package J3_6;

import java.util.*;

public class test {
    //你被请来给一个要举办高尔夫比赛的树林砍树。树林由一个 m x n 的矩阵表示， 在这个矩阵中：
    //
    //0 表示障碍，无法触碰
    //1 表示地面，可以行走
    //比 1 大的数 表示有树的单元格，可以行走，数值表示树的高度
    //每一步，你都可以向上、下、左、右四个方向之一移动一个单位，如果你站的地方有一棵树，那么你可以决定是否要砍倒它。
    //
    //你需要按照树的高度从低向高砍掉所有的树，每砍过一颗树，该单元格的值变为 1（即变为地面）。
    //
    //你将从 (0, 0) 点开始工作，返回你砍完所有树需要走的最小步数。 如果你无法砍完所有的树，返回 -1 。
    //
    //可以保证的是，没有两棵树的高度是相同的，并且你至少需要砍倒一棵树。
    class Solution {
        int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        public int cutOffTree(List<List<Integer>> forest) {
            List<int[]> trees = new ArrayList<int[]>();
            int row = forest.size();
            int col = forest.get(0).size();
            for (int i = 0; i < row; ++i) {
                for (int j = 0; j < col; ++j) {
                    if (forest.get(i).get(j) > 1) {
                        trees.add(new int[]{i, j});
                    }
                }
            }
            Collections.sort(trees, (a, b) -> forest.get(a[0]).get(a[1]) - forest.get(b[0]).get(b[1]));
            int cx = 0;
            int cy = 0;
            int ans = 0;
            for (int i = 0; i < trees.size(); ++i) {
                int steps = bfs(forest, cx, cy, trees.get(i)[0], trees.get(i)[1]);
                if (steps == -1) {
                    return -1;
                }
                ans += steps;
                cx = trees.get(i)[0];
                cy = trees.get(i)[1];
            }
            return ans;
        }
        public int bfs(List<List<Integer>> forest, int sx, int sy, int tx, int ty) {
            if (sx == tx && sy == ty) {
                return 0;
            }

            int row = forest.size();
            int col = forest.get(0).size();
            int step = 0;
            Queue<int[]> queue = new ArrayDeque<int[]>();
            boolean[][] visited = new boolean[row][col];
            queue.offer(new int[]{sx, sy});
            visited[sx][sy] = true;
            while (!queue.isEmpty()) {
                step++;
                int sz = queue.size();
                for (int i = 0; i < sz; ++i) {
                    int[] cell = queue.poll();
                    int cx = cell[0], cy = cell[1];
                    for (int j = 0; j < 4; ++j) {
                        int nx = cx + dirs[j][0];
                        int ny = cy + dirs[j][1];
                        if (nx >= 0 && nx < row && ny >= 0 && ny < col) {
                            if (!visited[nx][ny] && forest.get(nx).get(ny) > 0) {
                                if (nx == tx && ny == ty) {
                                    return step;
                                }
                                queue.offer(new int[]{nx, ny});
                                visited[nx][ny] = true;
                            }
                        }
                    }
                }
            }
            return -1;
        }
    }


    //给你一个 m x n 的迷宫矩阵 maze （下标从 0 开始），矩阵中有空格子（用 '.' 表示）和墙（用 '+' 表示）。同时给你迷宫的入口 entrance ，用 entrance = [entrancerow, entrancecol] 表示你一开始所在格子的行和列。
    //
    //每一步操作，你可以往 上，下，左 或者 右 移动一个格子。你不能进入墙所在的格子，你也不能离开迷宫。你的目标是找到离 entrance 最近 的出口。出口 的含义是 maze 边界 上的 空格子。entrance 格子 不算 出口。
    //
    //请你返回从 entrance 到最近出口的最短路径的 步数 ，如果不存在这样的路径，请你返回 -1 。
    public int nearestExit(char[][] maze, int[] entrance) {
        List<int[]> arr = findExport(maze);
        int n = arr.size();
        int sx = entrance[0];
        int sy = entrance[1];
        int min = Integer.MAX_VALUE;
        boolean hasMin = false;
        while (n != 0) {
            int tx = arr.get(n-1)[0];
            int ty = arr.get(n-1)[1];
            int path = goToExport(maze,sx,sy,tx,ty);
            if (path>0) {
                min = path<min?path:min;
                hasMin = true;
            }
            n--;
        }
        if (hasMin) {
            return min;
        }
        return -1;
    }
    public List<int[]> findExport(char[][] maze) {
        int row = maze.length;
        int low = maze[0].length;
        List<int[]> arr = new ArrayList<int[]>();
        for (int i = 0; i < row; i++) {
            if (maze[i][0] == '.') {
                arr.add(new int[]{i,0});
            }
            if (maze[i][low-1] == '.') {
                arr.add(new int[]{i,low-1});
            }
        }
        for (int i = 0; i < low; i++) {
            if (maze[0][i] == '.') {
                arr.add(new int[]{0,i});
            }
            if (maze[row-1][i] == '.') {
                arr.add(new int[]{row-1,i});
            }
        }
        return arr;
    }
    int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};
    public int goToExport(char[][] maze, int sx, int sy, int tx, int ty) {
        if (sx == tx && sy == ty) {
            return 0;
        }
        int row = maze.length;
        int low = maze[0].length;
        int step = 0;
        boolean[][] visited = new boolean[row][low];
        visited[sx][sy] = true;
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{sx,sy});
        while(!queue.isEmpty()) {
            step++;
            int sz = queue.size();
            while(sz != 0) {
                int[] cell = queue.poll();
                int x = cell[0], y = cell[1];
                for (int i = 0; i < 4; i++) {
                    int nx = x + dirs[i][0];
                    int ny = y + dirs[i][1];
                    if (nx>=0 && nx<row && ny>=0 && ny<low && !visited[nx][ny] && maze[nx][ny] != '+' ) {
                        if (nx == tx && ny == ty) {
                            return step;
                        }
                        queue.offer(new int[]{nx,ny});
                        visited[nx][ny] = true;
                    }
                }
                sz--;
            }
        }
        return -1;
    }


}
